package huisu;

import java.util.ArrayList;
import java.util.List;

public class AddOperator {

	public List<String> addOperators(String num, int target) {
		List<String> res = new ArrayList<String>();
		if(num == null || num.length() == 0){
			return res;
		}
		backtrack(res, "", num, target, 0, 0, 0);
		return res;
	}

	//path表示的是字符串表示的计算表达式：如： 1 + 2 * 3 + 4
	//eval表示的是计算的用字符串表示的结果
	
	public void backtrack(List<String> res, String path, String num, int target, int start, long eval, long multed){
		if(start == num.length()){
            if(target == eval){
                res.add(path);
            }
            return;
        }
		int length = num.length();
        for(int i = start; i < length; i++){
        	if(i != start && num.charAt(start) == '0'){
        		break;
        	}
        	//注意，因为是使用的字符串表示的数字，可能会出现overflow的情况，所以这里使用了long
        	long cur = Long.parseLong(num.substring(start, i + 1));
        	if(start == 0){
                backtrack(res, path + cur, num, target, i + 1, cur, cur);
            }else{
            	//eval是上一次计算出来的结果
                backtrack(res, path + "+" + cur, num, target, i + 1, eval + cur , cur);
                
                backtrack(res, path + "-" + cur, num, target, i + 1, eval -cur, -cur);
                
                //比如 5 + 6 * 7 eval计算出来是11（5 + 6），之后我们得修改为 5 + 6 * 7
                backtrack(res, path + "*" + cur, num, target, i + 1, eval - multed + multed * cur, multed * cur );
            }
        }
    }
}
